package MyArray;

/**
 * 240. 搜索二维矩阵 II
 *
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 *     每行的元素从左到右升序排列。
 *     每列的元素从上到下升序排列。
 */
public class Leetcode0240 {
    /**
     * 解题思路
     *
     * 因为 matrixmatrixmatrix 矩阵中每行的元素从左到右升序排列且每列的元素从上到下升序排列，所以可以从左下角（或右上角）开始查找。
     * 若当前矩阵的元素值 == target，则直接返回 true。
     * 若当前矩阵的元素值 > target，则向上移动一行列不变，
     * 即 matrix[i][j] 变为 matrix[i - 1][j]，继续进行比较。
     * 若当前矩阵的元素值 < target，则向右移动一列行不变，
     * 即 matrix[i][j] 变为 matrix[i][j + 1]，继续进行比较。
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int i = m - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] >target) {
                i--;
            } else {
                j++;
            }
        }
        return false;
    }
}
